1. Field
The present disclosure relates to the decoding of low-density parity-check (LDPC) codes. More in particular, it relates to methods for improving the performance of iterative decoders for LDPC codes which may be used with modulation levels above simple binary signaling.
2. Description of Related Art
As known to the person skilled in the art and as also mentioned in U.S. Pat. No. 7,343,539 incorporated herein by reference in its entirety, a low-density parity-check (LDPC) code is a linear code determined by a sparse parity-check matrix H having a small number of 1 s per column. The code's parity-check matrix H can be represented by a bipartite Tanner graph wherein each column of H is represented by a transmitted variable node, each row by a check node, and each “1” in H by a graph edge connecting the variable node and check node that correspond to the column-row location of the “1”. The code's Tanner graph may additionally have non-transmitted variable nodes. Each check or constraint node defines a parity check operation. Moreover, the fraction of a transmission that bears information is called the rate of the code. An LDPC code can be encoded by deriving an appropriate generator matrix G from its parity-check matrix H. An LDPC code can be decoded efficiently using a well-known iterative algorithm that passes messages along edges of the code's Tanner graph from variable nodes to check nodes and vice-versa until convergence is obtained, or a certain number of iterations is reached.
Forward error correction using LDPC codes is being used for deep-space and other aerospace applications as described by K. S. Andrews, D. Divsalar, S. Dolinar, J. Hamkins, C. R. Jones, and F. Pollara in “The development of turbo and LDPC codes for deep-space applications,” Proceedings of the IEEE, 95(11):2142-2156, November 2007. A set of LDPC codes has been approved as an international standard by the Consultative Committee for Space Data Systems (CCSDS) (see “TM Synchronization and Channel Coding,” CCSDS 131.1-B-2. Blue Book, Issue 2. August 2011). The standard LDPC codes include a family of nine accumulate repeat-4 jagged accumulate (AR4JA) LDPC codes, available in any combination of three code rates (½, ⅔, and ⅘) and three input block lengths (1024, 4096, and 16384).
FIG. 24 shows a block diagram of a system in which LDPC encoding is used for the transmission of information. As shown in FIG. 24, an encoder 110 applies the selected LDPC encoding scheme. A modulator 120 is then used to apply modulation to encoded characters. Since the information will be transmitted within a noisy environment (as is seen with free-space transmission) noise is modeled as being additive 150. A demodulator 130 is used to demodulate a received signal. A decoder 140 is used to decode the demodulated signal to recover the original information. These various components will be described in additional detail below, along with the impact of noise.
The encoder 110 shown in FIG. 24 will be discussed first. Since the AR4JA LDPC codes are binary, linear codes, encoding is accomplished by multiplying, in GF(2), an information vector by a generator matrix. The AR4JA codes have a number of features that simplify the encoding process. First, they are systematic, which means the information bits appear unchanged in the encoded codeword. Therefore, only the final n−k columns of the k×n generator matrix need be stored by the encoder. The codes are also quasi-cyclic, which is a result of using circulants to permute edges of the protograph copies. An encoder storing only rows 1, m+1, 2m+1, . . . , where m is the circulant size, may generate the other rows on the fly using shift registers.
In a software implementation, it may remain most convenient and efficient to store the last n−k columns of the generator matrix in their entirety, not making use of the quasi-cyclic property, and performing the encoding operation using standard matrix multiplication. In a high-level language such as C, individual bit operations are not as efficient as operations that are applied on registers that are 32 or 64 bits wide. Therefore, in C it is efficient to break each of the n−k columns into 64-bit segments, and store each segment in a 64-bit wide “long int” data structure. In this way, in one operation, 64-bits of information can be XORed with a 64-bit portion of the generator column, and the final codebit determined from the parity of all such 64-bit operations of the column. Since the input lengths of each of the AR4JA codes are a multiple of 64, this approach makes efficient use of the 64-bit data structures.
Possible implementations of the modulator 120 shown in FIG. 24 are discussed below. Several modulation types are described below, along with their associated complex signal constellations, default indexing, and average complex baseband energy. The signal constellations for these modulations are shown in FIGS. 1A-1E. In summary, the modulations discussed below include: Binary Phase Shift Keyed (BPSK); Quadrature Phase Shift Keyed (QPSK), 8 Phase Shift Keyed (8-PSK); 16 Amplitude Phase Shift Keyed (16-APSK), and 32 Amplitude Phase Shift Keyed (32-APSK).
BPSK is a real-valued constellation with two signal points: c(0)=A and c(1)=−A, where A is a scaling factor. This constellation is shown in FIG. 1A. The average complex baseband symbol energy is Es=E[c(i)2]=A2.
QPSK is a complex constellation with four signal points, with
            c      ⁡              (        i        )              =                  2            ⁢      A      ⁢                          ⁢              exp        ⁡                  [                      j            ⁢                          π              2                        ⁢                          (                              ⅈ                +                                  1                  2                                            )                                ]                      ,for i=0, 1, 2, 3. This constellation is shown in FIG. 1B. It is convenient to include the √{square root over (2)} factor so that the average symbol energy is Es=E[∥c(i)∥2]=2A2, double that of BPSK, but with the same energy per transmitted bit as BPSK.
8-PSK has constellation points
            c      ⁡              (        ⅈ        )              =          A      ⁢                          ⁢              exp        ⁡                  [                      j            ⁢                          π              4                        ⁢                          (                              ⅈ                +                                  1                  2                                            )                                ]                      ,for i=0, 1, . . . , 7. This constellation is shown in FIG. 1C. In general, M-PSK has constellation points
            c      ⁡              (        ⅈ        )              =          A      ⁢                          ⁢              exp        ⁡                  [                      j            ⁢                                          2                ⁢                π                            M                        ⁢                          (                              ⅈ                +                                  1                  2                                            )                                ]                      ,for i=0, 1, . . . , M−1. The average symbol energy is Es=E[∥c(i)∥2]=A2.
16-APSK is a standard of the second generation Digital Video Broadcast for Satellites. It is also referred to as 12/4 APSK or 12/4 QAM. It consists of the union of amplitude-scaled QPSK and 12-PSK signal constellations as shown in Eq. 1 below and the constellation shown in FIG. 1D.
                              c          ⁡                      (            ⅈ            )                          =                  {                                                                                          r                    1                                    ⁢                                      exp                    ⁡                                          [                                              j                        ⁢                                                  π                          2                                                ⁢                                                  (                                                      ⅈ                            +                                                          1                              2                                                                                )                                                                    ]                                                                                                                                        ⅈ                    =                    0                                    ,                  1                  ,                  2                  ,                  3                                                                                                                          r                    2                                    ⁢                                      exp                    ⁡                                          [                                              j                        ⁢                                                  π                          6                                                ⁢                                                  (                                                      ⅈ                            +                                                          1                              2                                                                                )                                                                    ]                                                                                                                                        ⅈ                    =                    4                                    ,                  5                  ,                  …                  ⁢                                                                          ,                  15                                                                                        Eq        .                                  ⁢        1            
The DVB-S2 standard defines the ratio r2/r1=3.15, 2.85, 2.75, 2.70, 2.60, and 2.57 for code rates ⅔, ¾, ⅘, ⅚, 8/9, and 9/10, respectively. The DVB-S2 standard does not specify use of a rate ½ code with 16-APSK; for the simulations described herein, r2/r1=3.15 when a rate ½ code is used. The average symbol energy is E=E[∥c(i)∥2]=(r12+3r22)/4.
FIG. 2 shows the required Eb/N0 to achieve CWER=10−3 for r=½, k=1024 AR4JA coded 16-APSK, as a function of the outer-to-inner ring ratio r2/r1. Although there is variation, the sensitivity is quite small. The optimal ratio for this coded modulation combination is about 3.15. For code-modulation combinations specified by DVB-S2, the simulations reported herein used the standard ratios. For rate modulation combinations not in the DVB-S2 standard, the ratios were first optimized using data as shown in FIG. 2, and then subsequent simulations were run with the optimized ratios.
32-APSK is also a DVB-S2 standard. It is the union of three PSK constellations as shown in Eq. 2 below and the constellation shown in FIG. 1E
                              c          ⁡                      (            ⅈ            )                          =                  {                                                                                          r                    1                                    ⁢                                      exp                    ⁡                                          [                                              j                        ⁢                                                  π                          2                                                ⁢                                                  (                                                      ⅈ                            +                                                          1                              2                                                                                )                                                                    ]                                                                                                                                        ⅈ                    =                    0                                    ,                  1                  ,                  2                  ,                  3                                                                                                                          r                    2                                    ⁢                                      exp                    ⁡                                          [                                              j                        ⁢                                                  π                          6                                                ⁢                                                  (                                                      ⅈ                            -                            4                            +                                                          1                              2                                                                                )                                                                    ]                                                                                                                                        ⅈ                    =                    4                                    ,                  5                  ,                  …                  ⁢                                                                          ,                  15                                                                                                                          r                    1                                    ⁢                                      exp                    ⁡                                          [                                              j                        ⁢                                                  π                          8                                                ⁢                        ⅈ                                            ]                                                                                                                                        ⅈ                    =                    16                                    ,                  17                  ,                  …                  ⁢                                                                          ,                  31                                                                                        Eq        .                                  ⁢        2            
The DVB-S2 standard defines the ratios r2/r1=2.84, 2.72, 2.64, 2.54, and 2.53, and r3/r1=5.27, 4.87, 4.64, 4.33, and 4.30 for code rates ¾, ⅘, ⅚, 8/9, and 9/10, respectively. The DVB-S2 standard does not specify use of rate ½ or ⅔ codes with 32-APSK; for the simulations described herein, r2/r1=4.0 and 3.15 and r3/r1=8.0 and 6.25 are used when rate ½ and ⅔ codes, respectively, are used. The average symbol energy is Es=E[∥c(i)∥2]=(r12+3r22+4r32)/8.
Encoded bits are assigned to a sequence of corresponding complex constellation points, or modulation symbols. Each of the modulations considered in this disclosure has a number of constellation points that is a power of two, which makes such bit-to-symbol mappings straightforward.
The signal constellations described above define a natural binary ordering. For example, the 8-PSK constellation points indexed by i=0, 1, 2, 3, 4, 5, 6, and 7 correspond to the 3-bit patterns 000, 001, 010, 011, 100, 101, 110, and 111, respectively. This may be referred to as the natural bit-to-symbol mapping for the modulation. Note that the natural ordering, or any other, is dependent on the way the constellation points happen to be indexed which, in principle, is arbitrary.
Other mappings, such as Gray codes, can often give better performance. Note that a Gray code may be more properly referred to as a Gray labeling. A code's word error rate performance is not dependent on the order of indexing, whereas with a Gray labeling, the whole point is that it is defined in a particular order. There are many Gray codes with the defining property that adjacent members in the list differ in exactly one bit in their binary representation, some with slightly different performance than others. In the simulations discussed herein, the binary reflected Gray code is used, which has recently been proven to be the optimal Gray code for M-PSK modulations (see, for example, E. Agrell, J. Lassing, E. G. Strom, and T. Ottosson, “On the optimality of the binary reflected Gray code,” IEEE Trans. Inform. Theory, 50(12):3170-3182, 2004.). The binary reflected Gray code of length M is obtained from the binary reflected Gray code of length M/2 by listing the members 0, 1, . . . , M−1, each preceded by a zero, followed by the members M−1, M−2, . . . , 0, each preceded by a one.
The binary reflected Gray code has the prefix property, i.e., a length M′ Gray code's members are equal to the first M′ members of a Gray code of length M, M>M′. Thus, when conducting simulations of Gray codes of various lengths, only the longest Gray code need be stored.
An anti-Gray code has the property that adjacent members in the list differ either in all their bits or in all but one of their bits. An anti-Gray code of length M can be obtained from a binary reflected Gray code of length M by removing the last M/2 entries and inserting after each of the remaining M/2 entries the ones complement of that entry. Anti-Gray codes do not have a prefix property, meaning a separate mapping should be stored for each length.
For modulations in which constellation points have more than two near neighbors, a specialized bit to symbol mapping is needed. The DVB-S2 standard specifies such a mapping to use with 16-APSK and 32-APSK.
The bit representations of the constellation points under the natural, Gray, anti-Gray, and DVB mappings are shown in FIG. 3, for lengths 2, 4, 8, 16, and 32. Note that in the Gray column, 0, 1, 3, 2, . . . in binary is 00000, 00001, 00011, 00010, . . . , and each subsequent constellation point has a binary representation that differs in exactly one bit, including wrapping around to the beginning. The anti-Gray column has a separate specification for each length and, for example, 0, 7, 1, 6, . . . , in binary is 000, 111, 001, 110, . . . , with each entry differing in either two or all three bits. In FIGS. 1A-1E, the BPSK, QPSK, and 8-PSK modulations are shown with the Gray code, and the 16-APSK and 32-APSK modulations are shown with the DVB-S2 standard mapping.
FIG. 3 gives a mapping from the constellation index i to the bit representation map(i), but, at the modulator, the inverse operation is used, to map bits to a constellation point. The inverse is defined by cm[map(i)]=c(i) for each i, where the subscript m indicates that the constellation has been mapped to a new ordering. For example, to map “1000” to a constellation point using the Gray code, note that “1000” is 8 in decimal, and cm[8]=c(15) is the corresponding constellation point.
FIG. 4 shows the performance of the r=½, k=1024 AR4JA code with 8-PSK when the bit-to-symbol mapping is Gray, natural, and anti-Gray. At BER=10−6, a natural mapping incurs a loss of 2.8 dB compared to the Gray code, and an anti-Gray code incurs a loss of 4.1 dB compared to the Gray code. It is important for system designers, therefore, to use a Gray mapping when using LDPC codes and higher order modulations.
As discussed above in regard to FIG. 24, noise may be modeled in a communication channel as being additive. To isolate the coded modulation performance from other effects, an additive white Gaussian noise (AWGN) channel with no Doppler, fading, or other channel impairments, no amplifier distortions, and perfect receiver synchronization of carrier frequency, phase, and timing is assumed herein.
The passband signal is assumed to be of the form shown in Eq. 3 below:s(t)=a(t)cos(2πfct+θ(t))  Eq. 3where fc is the carrier frequency in Hz, and a(t) and θ(t) are arbitrary modulation-dependent signals. Eq. 3 may be rewritten as shown in Eq. 4 below:s(t)=Re{{tilde over (s)}(t)ej2πfct}  Eq. 4where {tilde over (s)}(t)=a(t)ejθ(t) is the complex baseband representation of s(t). Eq. 5 below presents an alternative expression for {tilde over (s)}(t):{tilde over (s)}(t)=√{square root over (Pc)}+{tilde over (m)}(t)  Eq. 5where √{square root over (Pc)} is an unmodulated residual carrier signal with complex baseband power Pc, and {tilde over (m)}(t) is a complex baseband modulation with complex baseband power
      P    d    =            lim              T        ->        ∞              ⁢                  1        T            ⁢                        ∫          0          T                ⁢                                                            m                ~                            2                        ⁡                          (              t              )                                ⁢                                    ⅆ              t                        .                              
This can be put back in passband notation using Eq. 4, from which the residual carrier signal term √{square root over (Pc)} cos(2πfct) is readily apparent. The modulations discussed herein have the form shown in Eq. 6 below:
                                          m            ~                    ⁡                      (            t            )                          =                              ∑                          i              =                              -                ∞                                      ∞                    ⁢                                    m              ⁡                              [                ⅈ                ]                                      ⁢                          p              ⁡                              (                                  t                  -                                      ⅈ                    ⁢                                                                                  ⁢                    T                                                  )                                                                        Eq        .                                  ⁢        6            where m[i] is a member of a signal constellation m[i]εC={c(0), c(1), . . . , c(M−1)} in the complex plane, and where p(t) is a square pulse shape of symbol duration T as shown in Eq. 7 below:
                              p          ⁡                      (            t            )                          =                  {                                                    1                                                                                  if                    ⁢                                                                                  ⁢                    0                                    ≤                  t                  <                  T                                                                                    0                                            otherwise                                                                        Eq        .                                  ⁢        7            
For the purposes of this disclosure, the residual carrier signal can be assumed to have been filtered out of the modulated received signal or, equivalently, Pc=0. Thus, the received modulated complex baseband signal is of the form shown in Eq. 8 below:{tilde over (r)}(t)={tilde over (m)}(t)+ñ(t)  Eq. 8where ñ(t) is a complex baseband Gaussian noise process with one-sided power-spectral density N0 in each dimension. As the receiver, {tilde over (r)}(t) is put through a perfect matched filter, which results in complex soft symbols as shown in Eq. 9 below:r[i]=m[i]+n[i]  Eq. 9where n[i] is a complex Gaussian random variable with variance σ2 in each of its real and imaginary components.
The performance of the AR4JA LDPC codes on a binary-input additive white Gaussian noise (AWGN) channel is well-documented (see, for example, “The development of turbo and LDPC codes for deep-space applications,” and “Low density parity check codes for use in near-Earth and deep space,” cited above). Such published performance results apply to binary phase-shift keying (BPSK) or quadrature PSK (QPSK) modulation, as is typically used in deep space missions. When bandwidth is constrained, however, system engineers may also desire to know the performance of LDPC codes when used with higher order modulations, in order to most effectively trade off power efficiency, bandwidth efficiency, and complexity. The need for bandwidth-efficient higher order modulations will become more pressing in the future as NASA and other space agencies utilize higher data rates and more simultaneous missions in the same limited spectrum. Modern variable coded modulation (VCM) or adaptive coded modulation (ACM) schemes will be able to switch between the different coded modulations as power and bandwidth resources vary.
Therefore, it is helpful to assess the performance of the standard LDPC codes when used with higher order modulations such as 8-PSK, 16-ary amplitude PSK (16-APSK), and 32-APSK. The performance of rate ⅘ AR4JA codes used with BPSK, 8-PSK, and 16-APSK has been previously reported (see M. Cheng, D. Divsalar, and S. Duy “Structured low-density parity-check codes with bandwidth efficient modulation,” In Proceedings of SPIE Conference on Defense Security and Sensing, April 2009). For other combinations of codes and modulations, performance may be estimated based on the concept of code imperfectness. First, the code imperfectness of the code when used with BPSK is determined by measuring the difference between the code's required bit signal to noise ratio Eb/N0 to attain a given codeword error rate (CWER) and the minimum possible Eb/N0 required to attain the same CWER as implied by the sphere-packing bounds for codes with the same block size k and code rate r (see S. Dolinar, D. Divsalar, and F. Pollara, “Code performance as a function of block size,” TDA Progress Report, 42(133), May 1998). This same imperfectness is then applied with respect to the capacity of the higher order modulation to arrive at an approximated performance of the code when used with the higher order modulation. The imperfectness approximation has generally been found to be fairly accurate, to within about 0.5 dB, over a wide variety of codes and modulations.
The presence of noise in the channel makes the selection and implementation of a decoder (such as the decoder 140 shown in FIG. 24) important, since the decoder must properly recover the transmitted information in the presence of noise. Some LDPC decoder implementations may require a long time to process received data to recover transmitted information or may not be able to recover information at a desired error rate at all. Therefore, there exists a need in the art for LDPC decoder variations that can provide desired performance.